Thuật toán tiến hóa là gì? Các nghiên cứu khoa học liên quan

Định nghĩa thuật toán tiến hóa

Thuật toán tiến hóa (Evolutionary Algorithm, EA) là phương pháp tối ưu hóa và tìm kiếm giải pháp dựa trên nguyên lý chọn lọc tự nhiên, di truyền học và cơ chế tiến hóa sinh học. Khởi đầu từ một quần thể các cá thể (mỗi cá thể biểu diễn một giải pháp), EA áp dụng các toán tử như lai ghép (crossover), đột biến (mutation) và chọn lọc (selection) để tạo ra thế hệ mới với hy vọng gia tăng chất lượng tổng thể.

Mỗi cá thể được mã hóa dưới dạng chuỗi gen (binary string, vector số thực hoặc cây biểu thức) và đánh giá bằng hàm thích nghi (fitness function). Giá trị fitness xác định khả năng "sống sót" và "sinh sản" của cá thể, từ đó những cá thể có fitness cao sẽ có xác suất sinh con cao hơn, dần hình thành quần thể hội tụ về giải pháp tối ưu.

Quá trình tiến hóa lặp đi lặp lại cho đến khi đạt điều kiện dừng: số thế hệ tối đa, fitness đạt ngưỡng hoặc không có cải thiện đáng kể. EA có ưu điểm khả năng tìm kiếm toàn cục, không yêu cầu tính khả vi hay liên tục của hàm mục tiêu, phù hợp với các bài toán phức tạp, nhiễu và đa cực trị.

Lịch sử và phát triển

Năm 1954, Rosenblatt đề xuất ý tưởng Perceptron với phần học dựa trên điều chỉnh trọng số gợi nhớ cơ chế tiến hóa của tự nhiên. Thập niên 1960–1970, Fraser và Schwefel phát triển Evolution Strategies (ES) tại Đức, tập trung vào tối ưu hóa số thực và điều chỉnh kích thước bước nhảy.

Trong cùng thời kỳ, Fogel, Owens và Walsh ở Hoa Kỳ giới thiệu Evolutionary Programming (EP), tập trung vào cải tiến cấu trúc và hành vi của các chương trình máy tính. Sang thập niên 1980, John Holland hệ thống hóa Genetic Algorithms (GA), đưa ra mô hình lai ghép và chọn lọc dùng chuỗi nhị phân.

Đến năm 1992, thuật ngữ chung Evolutionary Algorithm xuất hiện, bao quát GA, ES, EP và mở ra kỷ nguyên nghiên cứu EA tổng quát. Từ đó đến nay, cộng đồng nghiên cứu phát triển đa dạng biến thể: từ multi-objective EA (NSGA-II) đến các thuật toán lai ghép với học máy, mở rộng ứng dụng sang xử lý ảnh, học sâu và tối ưu hóa công nghiệp.

Phân loại chính

Thuật toán tiến hóa chia theo cấu trúc và cách mã hóa cá thể, gồm bốn nhóm chính:

• Genetic Algorithms (GA): cá thể mã hóa dưới dạng chuỗi nhị phân hoặc số thực, sử dụng lai ghép đa điểm và đột biến bit.
• Evolution Strategies (ES): tối ưu hóa số thực, cá thể mang tham số đột biến, tự điều chỉnh biến thể đột biến.
• Evolutionary Programming (EP): tập trung vào đột biến mạnh, không dùng lai ghép, phù hợp với tối ưu hóa hành vi và mô hình thời gian thực.
• Genetic Programming (GP): mã hóa cá thể dưới dạng cây biểu thức, thích hợp cho sinh chương trình máy tính hoặc phát hiện quy tắc.

Loại EA	Mã hóa	Toán tử chính	Ứng dụng tiêu biểu
GA	Chuỗi nhị phân/số thực	Lai ghép (crossover), Đột biến (mutation)	Tối ưu rời rạc, thiết kế mạng lưới
ES	Vector số thực	Đột biến có phân phối Gaussian	Tối ưu hàm số liên tục, điều khiển robot
EP	Biểu diễn hành vi	Đột biến mạnh	Mô hình hóa hệ thống động
GP	Cây biểu thức	Lai ghép cây, Đột biến cây	Khám phá quy tắc, lập trình tự động

Các biến thể kết hợp giữa GA và ES hay tích hợp với mạng nơ-ron ngày càng phổ biến, khai thác ưu điểm của từng phương pháp để tăng hiệu suất và tính khả dụng trong thực tiễn.

Cơ sở sinh học

EA mô phỏng quá trình tiến hóa sinh học gồm bốn nguyên lý cốt lõi: chọn lọc tự nhiên (natural selection), di truyền (inheritance), lai ghép (recombination) và đột biến (mutation). Chọn lọc tự nhiên đảm bảo các cá thể có fitness cao có xác suất cao truyền gen sang thế hệ tiếp theo.

Lai ghép tái phối hợp gen giữa hai cá thể, tương tự giao phối sinh học, giúp khám phá không gian giải pháp mới. Đột biến biến đổi gen ngẫu nhiên, duy trì đa dạng di truyền, giảm nguy cơ hội tụ sớm vào nghiệm cục bộ.

Quá trình này lặp đi lặp lại qua các thế hệ, tích lũy dần các đặc tính ưu việt và loại bỏ dần các gen kém thích nghi, dẫn đến quần thể hội tụ về giải pháp tối ưu hoặc gần tối ưu theo tiêu chí định trước.

Thành phần chính và toán tử

Thuật toán tiến hóa bao gồm sáu thành phần cơ bản: khởi tạo quần thể, đánh giá fitness, chọn lọc, lai ghép, đột biến và thay thế. Quần thể ban đầu P₀ thường được tạo ngẫu nhiên hoặc dựa trên kinh nghiệm, đảm bảo đa dạng khởi tạo.

Đánh giá fitness ánh xạ mỗi cá thể thành giá trị số, thể hiện chất lượng giải pháp. Hàm fitness có thể là hàm mục tiêu đơn hoặc đa mục tiêu; với bài toán đa mục tiêu, EA thường sử dụng công cụ như NSGA-II để phân loại cá thể theo biên Pareto citeieeexplore.ieee.org/document/996017.

Chọn lọc (selection) xác định cá thể làm cha mẹ cho thế hệ sau. Các phương pháp phổ biến bao gồm:

• Roulette wheel: xác suất chọn tỉ lệ thuận với fitness.
• Tournament: ngẫu nhiên chọn nhóm nhỏ và chọn cá thể tốt nhất trong nhóm.
• Rank selection: sắp xếp cá thể theo fitness rồi phân phối xác suất đều hơn.

Lai ghép (crossover) kết hợp gen từ hai cha mẹ để tạo con, thường dùng một điểm (one-point) hoặc đa điểm (multi-point) với chuỗi nhị phân, hoặc crossover tuyến tính cho vector số thực. Đột biến (mutation) thay đổi ngẫu nhiên một phần gen để duy trì đa dạng di truyền.

Toán tử	Chuỗi nhị phân	Số thực
One-point crossover	Đảo chéo tại vị trí ngẫu nhiên	Không áp dụng
Arithmetic crossover	Không áp dụng	$<\alpha x_i + (1-\alpha) y_i>$
Bit-flip mutation	Đổi 0⇄1 với xác suất p	Không áp dụng
Gaussian mutation	Không áp dụng	Thêm nhiễu $N(0,\sigma^2)$

Biểu diễn và mã hóa

Cách mã hóa cá thể ảnh hưởng trực tiếp đến hiệu quả tìm kiếm. Các dạng mã hóa phổ biến:

• Binary string: mã hóa bit phù hợp với bài toán rời rạc, dễ áp dụng toán tử bit-flip và crossover.
• Real-valued vector: phù hợp với tối ưu hóa liên tục, cho phép sử dụng toán tử số học và đột biến Gaussian.
• Expression tree: trong Genetic Programming, cá thể là cây biểu thức đại diện cho chương trình hoặc công thức toán học.

Ví dụ mã hóa số thực cho biến x, y:

1. Khởi tạo ngẫu nhiên trong khoảng $[a,b]$.
2. Áp dụng arithmetic crossover: $z_i = \alpha x_i + (1-\alpha) y_i$.
3. Mutation theo Gaussian: $x_i' = x_i + N(0,\sigma^2)$.

Ưu điểm của mã hóa số thực là giảm số tham số và cho phép khám phá gradient ngẫu nhiên, tuy nhiên dễ rơi vào extrema cục bộ nếu p_mutation quá thấp.

Hàm thích nghi (Fitness Function)

Hàm thích nghi xác định độ “tốt” của mỗi cá thể. Với bài toán tối ưu đơn mục tiêu, thường dùng giá trị hàm mục tiêu hoặc nghịch đảo chi phí. Với bài toán đa mục tiêu, EA sử dụng chiến lược không thống nhất (non-dominated sorting) như NSGA-II để phân hạng và duy trì đa dạng citeieeexplore.ieee.org/document/996017.

Trong một số trường hợp, fitness là hàm kết hợp nhiều tiêu chí:

$\text{fitness} = w_1 f_1(x) + w_2 f_2(x) + \dots + w_k f_k(x)$

trong đó $w_i$ là trọng số ưu tiên. Cần đảm bảo các hàm con $f_i$ cùng thang đo hoặc được chuẩn hóa để tránh thiên lệch.

Quy trình tổng quát

Quy trình thuật toán tiến hóa thường lặp lại theo sáu bước:

1. Khởi tạo quần thể P₀ với N cá thể.
2. Đánh giá fitness cho Pₜ.
3. Chọn lọc cá thể làm bố mẹ từ Pₜ.
4. Áp dụng lai ghép và đột biến để sinh quần thể con Qₜ.
5. Đánh giá fitness Qₜ và hợp nhất với Pₜ để tạo Pₜ₊₁.
6. Kiểm tra điều kiện dừng: số thế hệ, fitness tối đa hoặc hội tụ.

Sự kết hợp giữa chọn lọc elitist (giữ lại cá thể tốt nhất) và xác suất ngẫu nhiên giúp cân bằng giữa khai thác (exploitation) và khám phá (exploration).

Ứng dụng

Thuật toán tiến hóa có mặt trong nhiều lĩnh vực:

• Kỹ thuật: tối ưu thiết kế kết cấu, bố trí thiết bị, tối ưu luồng công việc trong sản xuất.
• Học máy: chọn tính năng, tối ưu siêu tham số cho mô hình học sâu.
• Tài chính: tối ưu danh mục đầu tư, mô hình định giá quyền chọn không tuyến tính.
• Điều khiển tự động: tinh chỉnh bộ điều khiển PID, lập kế hoạch chuyển động cho robot.

Các công cụ phổ biến như DEAP (Python) hay ECJ (Java) hỗ trợ nhanh việc triển khai và tùy biến EA cho bài toán cụ thể citesciencedirect.com/science/article/pii/S095741741100536X.

Ưu điểm và hạn chế

Ưu điểm: khả năng tìm kiếm toàn cục, không yêu cầu tính khả vi của hàm mục tiêu, dễ tích hợp với các phương pháp khác, xử lý tốt bài toán nhiễu và đa cực trị.

Hạn chế: chi phí tính toán lớn với kích thước quần thể và số thế hệ cao, dễ hội tụ sớm vào nghiệm cục bộ, hiệu quả phụ thuộc vào tham số thuật toán và cách mã hóa.

Tiêu chí	Ưu điểm	Hạn chế
Tìm kiếm toàn cục	Cao	Chi phí tính toán lớn
Yêu cầu gradient	Không	Khó điều chỉnh tham số
Khả năng mở rộng	Rộng rãi	Phụ thuộc dữ liệu khởi tạo

Tài liệu tham khảo

• IEEE – NSGA-II Multi-Objective Optimization
• Springer – A Brief History of Evolutionary Computation
• Expert Systems with Applications – Evolutionary Algorithm Applications
• ACM Computing Surveys – Survey of Evolutionary Computation